package Sort;

//堆排序
public class HeapSort {

    public static void sort(int[] a){
        heapify(a,a.length);
        for (int right = a.length - 1; right > 0 ; right--) {
            swap(a,0,right);
            down(a,0,right);
        }
    }
    //建堆
    private static void heapify(int[] array,int size){
        for (int i = size / 2 - 1; i >=0 ; i--) {
            down(array,i,size);
        }
    }
    //下潜
    private static void down(int[] array, int parent,int size){
        while(true){
            int left = parent * 2 + 1;
            int right = left + 1;
            int max = parent;
            if(left < size && array[left] > array[max]){
                max = left;
            }
            if(right < size && array[right] > array[max]){
                max = right;
            }
            if(max == parent){
                break;
            }
            swap(array,max,parent);
            parent = max;
        }
    }
    //交换
    private  static void swap(int[] a,int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
